#include <stdio.h>
typedef struct {
	int map[3][3];
}tobo;
tobo rotate(tobo from, int dir, int place) {
	int i;
	tobo to=from;
	for(i=0;i<4;i++)
		to.map[(place>>1)+(i>>1)][(place&1)+(i&1)]
			=from.map[(place>>1)+(dir^(i&1))][(place&1)+(dir^(i>>1)^1)];
	return to;
}
int maxdep, ans=-1;
#define ABS(a) (a>0?a:-(a))
int h(tobo a) {
	int ret=0,i,j;
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
			ret += ABS(i-(a.map[i][j]-1)/3)+ABS(j-((a.map[i][j]-1)%3));
	return (ret+3)>>2;
}
void ida(int dep, tobo cur) {
	if(dep+h(cur)>maxdep)
        return;
    if(h(cur)==0){
        ans=ans==-1?dep:ans<dep?ans:dep;
        maxdep=ans;
        return;
    }
    int i,j;
    for(i=0;i<2;i++)
        for(j=0;j<4;j++)
            ida(dep+1,rotate(cur,i,j));
}
int main() {
	int i,j,dep,time;
	char c;
	tobo from;
	for(time=1;;time++) {
		scanf(" %c",&c);
		maxdep=c-'0';
		for(i=0;i<3;i++)
			for(j=0;j<3;j++)
				from.map[i][j]=getchar()-'0';
		if(from.map[1][1]==0)
			break;
        ans=-1;
        ida(0,from);
        printf("\n%d. %d",time,ans);
	}
	return 0;
}